package 位运算;

public class JZ56数组中数字出现的次数I {

    /**
     * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。
     * 请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
     *
     * 示例 1：
     * 输入：nums = [4,1,4,6]
     * 输出：[1,6] 或 [6,1]
     * 示例 2：
     * 输入：nums = [1,2,10,4,1,4,3,3]
     * 输出：[2,10] 或 [10,2]
     *  
     * 限制：
     * 2 <= nums.length <= 10000
     */

    /**
     * 1.先O(n)遍历异或所有元素,得到两个不同数字的异或结果
     * 2.再找到异或结果从左到右第一个不为0的下标偏移量
     * 3.然后再O(n)遍历所有元素,对偏移量进行异或分为两组,这样可以得到两组数字,
     *   并且保证 a组中仅有一个单独元素  b组中仅有一个单独元素,
     *   然后就可以得到两组分别的那个单独元素
     */
    public int[] singleNumbers(int[] nums) {

        int res=0;

        for (int i = 0; i < nums.length; i++) {
            res^=nums[i];
        }

        //得到两个单独数的异或结果->res
        //找到第一位不为0的偏移量
        int num=1;
        while ((res&num)==0){
            num<<=1;
        }
        //然后分组
        int res1=0;
        int res2=0;
        for (int i : nums) {
            if((i&num)==0){
                res1^=i;
            }else{
                res2^=i;
            }
        }

        return new int[]{res1,res2};
    }

    public static void main(String[] args) {
        System.out.println(Integer.parseInt("101011011",2));
        // 101011011
        int num=347;
        // 00001
        int res=1;

        //找到第一位不为0的偏移量
        while ((res&num)==1){
            res<<=1;
        }

        System.out.println(Integer.toBinaryString(res));
        System.out.println(res);
    }

}
